package com.datastructure.test.boxin;

import java.util.ArrayList;
import java.util.stream.Collectors;

public class BoxIn {

    public int minVolume = Integer.MAX_VALUE;
    public int current = 0;
    public static void main(String[] args) {
        BoxIn boxIn = new BoxIn();
        ArrayList<Integer> num = new ArrayList<>();
        num.add(8);
        num.add(3);
        num.add(12);
        num.add(7);
        num.add(9);
        int boxin = boxIn.boxin(24, num);
        System.out.println(boxin);
    }

    public int boxin (int V, ArrayList<Integer> num) {
        // write code here
        ArrayList<Integer> collect = (ArrayList<Integer>)num.stream().sorted().collect(Collectors.toList());
        dfs(0,V,collect);
        return minVolume;
    }

    private void dfs(int start,int v, ArrayList<Integer> num) {
        if(current>v){
            return;
        }
        if((v-current>=0)&&(v-current<minVolume)){
            minVolume=v-current;
        }
        if(current==v){
            return;
        }
        for (int i = start; i < num.size(); i++) {
            current+= num.get(i);
            dfs(i+1,v,num);
            current-= num.get(i);
        }
    }


    public int boxin1 (int V, ArrayList<Integer> num) {
        // write code here
        boolean[] dp = new boolean[V+1];
        dp[0] = true;
        for(int x : num) {
            for(int i = V; i >= x; --i) {
                dp[i] = dp[i] || dp[i-x];
            }
        }
        int m = V;
        while(!dp[m]) {
            --m;
        }
        return V - m;
    }
}
